// https://leetcode.cn/problems/first-missing-positive/description/?envType=study-plan-v2&envId=top-100-liked

// 算法思路总结：
// 1. 原地哈希将正整数放置到对应位置
// 2. 遍历数组交换元素到正确索引位置
// 3. 第二次遍历查找第一个位置不匹配的元素
// 4. 利用数组本身作为哈希表节省空间
// 5. 时间复杂度：O(n)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    int firstMissingPositive(vector<int>& nums) 
    {
        int m = nums.size();

        for (int i = 0 ; i < m ; i++)
        {
            while (0 < nums[i] && nums[i] <= m && nums[i] != nums[nums[i] - 1])
            {
                swap(nums[i], nums[nums[i] - 1]);
            }
        }

        for (int i = 0 ; i < m ; i++)
        {
            if (nums[i] != i + 1)
                return i + 1;
        }

        return m + 1;
    }
};

int main()
{
    vector<int> nums1 = {1,2,0}, nums2 = {3,4,-1,1};
    Solution sol;

    cout << sol.firstMissingPositive(nums1) << endl;
    cout << sol.firstMissingPositive(nums2) << endl;

    return 0;
}